//递推求组合数
for(int i = 1;i<=2005;i++)
{
    for (int j = 0; j <= i; j++) {
        if (i == j || j == 0) {
            ans[i][j] = 1;
        }
        else {
            ans[i][j] = (ans[i - 1][j] + ans[i - 1][j - 1]) % mod;
        }
    }
}
//求组合数2
typedef long long LL;
long long fac[N],infac[N];
void init()
{
    fac[0]=infac[0]=1;
    for(int i=1;i<=2e5;i++)
    {
        fac[i]=fac[i-1]*i%mod;
        infac[i]=(LL)infac[i - 1] * quick_pow(i,mod-2,mod)%mod;
    }
}

LL C(int a,int b)
{
    if(b == 0) return 1;
    if(a < b) return 0;
    return ((fac[a] * infac[b])%mod * infac[a - b]) % mod;
}


//求排列时：如果要向一个已经有 u 个球的盒子里放入 b 个数，那么方案数要乘上 C(b,u + b); 
